package 栈.有效的括号;

import java.util.Stack;
/**
 * 题目描述
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 * 输入：s = "()"
 * 输出：true
 * 力扣：https://leetcode-cn.com/problems/valid-parentheses/
 * 力扣第 20
 * */
/**
 * 题目思路：
 * 创建一个栈来存放括号
 * 将左括号压入栈中
 * 如果是右括号号，检查栈是否为空，以及栈顶元素是否与之匹配
 * */

class Solution {
    public boolean isValid(String s) {
       // 创建一个栈来存放括号
       Stack<Character> stack = new Stack<>();

       // 遍历字符串中的每个字符
       for(char c : s.toCharArray()){
         // 如果是开括号，压入栈中
         if(c == '(' || c == '[' || c == '{'){
            stack.push(c);
         }else{
            // 如果是闭括号，检查栈是否为空，以及栈顶元素是否与之匹配
            if(stack.isEmpty()){
                return false; // 栈为空，说明没有对应的开括号
            }
            // 检查栈顶元素
            char top = stack.pop();
            if((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')){
                return false; // 栈顶元素与当前闭括号不匹配
            }
         }
       }
       // 如果栈为空，说明所有括号都正确匹配
       return stack.isEmpty(); 
    }
}